1. Field of the Invention
The present invention relates to link state routing techniques in a network which is structured into single-level or multi-level hierarchy, and in particular to a link state routing device and method for determining an optimal path using topology information and quality-of-service (QoS) information of the entire network, which are obtained by exchanging route information including link or nodal topology information and QoS information between single peer group nodes or hierarchical peer group nodes in the network.
2. Description of the Related Art
A QoS routing algorithm for finding a path that guarantees QoS parameters requested by users has been proposed by IWATA et al. “ATM Routing Algorithms with Multiple QOS Requirements for Multimedia Internetworking” (IEICE Transactions on Communications, Vol. E79-B, No. 8, pp 999-1007, August 1996).
More specifically, the QoS routing algorithm includes a precalculated path approach and an on-demand calculated path approach. When receiving a connection setup request from a user, the precalculated path approach is performed to search a precalculated path resource information memory for a candidate path satisfying the QoS requirement of the connection setup request. If such a candidate path is found, then the connection is set up. Contrarily, when not found, the connection setup request is supplied to the on-demand calculated path approach.
The on-demand calculated path approach calculates a path satisfying the QoS requirement of the connection setup request based on link resource information stored in a link resource information memory. When such a path is found, then the connection is set up. Contrarily, when not found, the connection setup request is finally rejected.
The link resource information memory stores link resource information such as available bandwidth and delay for each link. When receiving link resource information from another node, it is determined whether any change in link resource information occurs in the link resource information memory. If any link resource information is changed, then the corresponding link resource information is updated.
In the case of a large hierarchical network, a border communication device is needed to exchange summarized link resource information between different-level nodes. Such a border communication device for link state routing has been proposed by Korkmaz et al. “Source-Oriented Topology Aggregation with Multiple QoS parameters in Hierarchical ATM Networks” (IEEE/IFIP IWQoS'99, pp. 137-146, Jun. 1999).
More specifically, such a border communication device is provided with a summarized information computation means. When the contents of a link resource information memory has been updated, the summarized information computation means summarizes network status of nodes in its own level while referring to the updated contents of the link resource information memory. The summarized information is sent to another level of the hierarchy.
There have been proposed various communication devices similar to the above communication devices. For example, Japanese Patent No. 2723097 discloses a QoS routing device capable of selecting a path satisfying all the QoS requirements of a connection setup request. Japanese Patent Application Unexamined Publication No. 11-252106 discloses a connection path changing device capable of re-establishing a connection so as to get around a designated node after connection establishment. Japanese Patent Application Unexamined Publication No. 10-164074 discloses an ATM network system capable of searching for a connection path satisfying QoS when routing in the network and also reducing the load of connection setup. Japanese Patent Application Unexamined Publication No. 10-135980 discloses a connection setup device avoiding causing an established connection to degrade the quality thereof and allowing rapid recovery of the connection. Japanese Patent Application Unexamined Publication No. 10-154979 discloses a point-to-multipoint connection method for setting up a point-to-multipoint call by selecting an economical connection path in a broad-band communications network.
A combination of path precalculation and dynamic route search employed in the conventional link-state routing devices as described above has disadvantages that there is often the case where a precalculated path satisfying the connection quality requirement is not found. The reason is that only a single precalculated path is used for each destination, resulting in a few candidate paths. This increases the number of times a path is dynamically calculated and thereby increases the load.
In addition, since the precalculated path information fails to reflect the latest path information, there is a high probability of connection setup failure.
As for the border communication device as described above, calculation of summarized information needs the high computing power because it is necessary to search the entire network of its own and repeatedly perform calculation with accuracy.
Further, the summarized information is sent to another level of the hierarchy every time when the network status of its own is updated. Therefore, the amount of packet data is increased, which may cause network congestion.